#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 *给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

 

示例 1：


输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

ListNode *reverseList(ListNode *head) {
    if ((head == nullptr) || head->next == nullptr) //如果最后一个结点不操作
        return head;
    ListNode *node = reverseList(head->next); //先递归到最底层 然后返回 即一直循环到链尾
    head->next->next = head; //翻转链表的指向
    head->next = nullptr; //记得赋值null 防止链表错乱
    return node; //新链表头永远指向的是原链表的链尾
}


// 1 2 3 4
//寻找尾结点
static ListNode *findK(ListNode *head, int k) {
    ListNode *headCheck = head;
    for (int i = k; i > 1; i--) {
        if (headCheck == nullptr)
            return nullptr;
        else
            headCheck = headCheck->next;
    }
    return headCheck;
}

static ListNode *rever(ListNode *head, int k) {
    ListNode *headCheck = head;
    //
    for (int i = k; i > 0; i--) {
        if (headCheck == nullptr)
            return head;
        else
            headCheck = headCheck->next;
    }
    //翻转链表
    ListNode *now = head;
    ListNode *end = nullptr;
    ListNode *lastNode = nullptr;
    ListNode *ret = findK(now, k);
    ListNode *endNext;
    while (true) {
        end = findK(now, k);
        //节点够可以翻转
        if (end != nullptr) {
            //获取end下一个
            endNext = end->next;
            end->next = nullptr;
            ListNode *retHead = reverseList(now);//翻转后的链表头
            //now->next=endNext;
            if (lastNode != nullptr) {
                lastNode->next = end;
            }

            lastNode = now;
            now = endNext;
        } else {
            if (lastNode != nullptr) {
                lastNode->next = endNext;
            }
            return ret;
        }


    }

    return ret;
}

//返回翻转后的头
ListNode *reverseKGroup(ListNode *head, int k) {
    ListNode *headCheck = head;
    //
    for (int i = k; i > 0; i--) {
        if (headCheck == nullptr)
            return head;
        else
            headCheck = headCheck->next;
    }

    //翻转链表
    int count = 0;
    ListNode *now = head;
    ListNode *firstPtr = nullptr;
    ListNode *nowNext = nullptr;

    //进行翻转
    while (count < k && now != nullptr) {
        //头插进行逆转
        nowNext = now->next;
        now->next = firstPtr;
        firstPtr = now;
        now = nowNext;
        count++;
    }

    //比如是2 3  三这边断开了
    //链接收尾1  2 3 | 4 5

    //用翻转后的尾结点链接 head 指向翻转后的链表尾部（因为head是头 反转后就是尾部）
    if (head != nullptr)
        head->next = reverseKGroup(now, k);


    return firstPtr;//返回头结点

}